W2. Базовые структуры данных, рекурсия и поиск с возвратом

Автор

Nikolai Kudasov

Дата публикации

29 января 2026 г.

1. Краткое содержание

1.1 Введение и предпосылки
1.1.1 Временная сложность и нотация Big-O

Прежде чем переходить к структурам данных, важно понять, как мы измеряем их эффективность. Временная сложность (time complexity) описывает, как время выполнения операции растёт при увеличении размера входа.

  • \(O(1)\) — константное время: операция занимает примерно одинаковое время независимо от размера входа. Пример: доступ к элементу массива по индексу arr[5] — один шаг.
  • \(O(n)\) — линейное время: время растёт пропорционально размеру входа \(n\). Пример: поиск в несортированном списке из \(n\) элементов — нужно проверить каждый.
  • \(O(\log n)\) — логарифмическое время: время растёт медленно при росте \(n\). Пример: binary search в отсортированном массиве из 1000 элементов — около 10 шагов (\(2^{10} = 1024\)).
  • \(O(n^2)\) — квадратичное время: время растёт как квадрат размера входа. Пример: сравнение каждой пары элементов списка.

Амортизированная сложность (amortized complexity) — среднее время на операцию в длинной последовательности операций с учётом редких «дорогих» шагов. Например, если вы добавляете 100 элементов в ArrayList и лишь один раз происходит resize с копированием всех элементов, большинство добавлений дёшевы, и amortized время добавления в конец остаётся \(O(1)\).

1.1.2 Указатели и ссылки

Указатель (pointer) (в Java и Python чаще говорят reference) — переменная, хранящая адрес другого объекта в памяти. Вместо самих данных она «указывает», где данные лежат.

Наглядно: как записка с адресом дома — сама записка не дом, но говорит, где его найти. В связных структурах каждый node хранит ссылку на следующий узел, образуя цепочку.

1.2 Абстрактные типы данных и структуры данных
1.2.1 Абстрактный тип данных (ADT)

Абстрактный тип данных (Abstract Data Type, ADT) — математическая модель, которая описывает тип данных только через поведение, без указания реализации. ADT можно мыслить как контракт или interface: он задаёт, какие операции доступны и какие правила они соблюдают, но не говорит, как это устроено внутри.

ADT определяет три вещи:

  • Операции и конструкторы, доступные для значений этого типа
  • Сигнатуры типов (type signatures) этих операций — какие входы они принимают и какие выходы возвращают
  • Свойства (laws), которым операции должны удовлетворять

Например, «Number» можно рассматривать как ADT: операции включают построение нуля, сложение (\(+\)) и т.д.; сигнатура \(+\) говорит, что она берёт два числа и возвращает число; свойство — \(x + y = y + x\) для любых \(x, y\). Аналогично «Set» — ADT с операциями вроде пустого множества, объединения (\(\cup\)) и свойствами вроде \(x \cup y = y \cup x\).

1.2.2 Структура данных

Структура данных (data structure) — конкретная реализация ADT. Если ADT задаёт что делает тип, то структура данных задаёт как — фактическое представление в памяти и алгоритмы для каждой операции.

Например, java.math.BigDecimal в Java — структура данных для десятичных чисел произвольной точности (цифры в списке и арифметика по нему). java.util.HashSet — структура данных для Set ADT на hash table с separate chaining.

1.2.3 Строительные блоки

Большинство структур строятся из двух базовых механизмов:

  • Непрерывный блок данных (array): элементы в соседних ячейках памяти — быстрый доступ по индексу.
  • Связная структура (linked structure): элементы в отдельных node со ссылками друг на друга — гибкие вставка и удаление.
1.3 Списки
1.3.1 List ADT

Список (List) — ADT упорядоченной последовательности элементов. От других последовательностей вроде Stack или Queue список отличается тем, что доступ, вставка и удаление возможны по произвольному индексу.

List ADT поддерживает операции:

  • создать пустой список;
  • size() — число элементов;
  • isEmpty() — пуст ли список;
  • get(i) — элемент с индексом \(i\);
  • set(i, e) — заменить элемент с индексом \(i\) на \(e\);
  • add(i, e) — вставить \(e\) в позицию \(i\), сдвинув хвост вправо;
  • remove(i) — удалить элемент с индексом \(i\), сдвинув хвост влево.

Пример: из [] добавим \(A\) в индекс 0 → [A]; добавим \(B\) в 0 → [B, A]; добавим \(C\) в 2 → [B, A, C]; get(1) вернёт \(A\); remove(1) даст [B, C].

В Java интерфейс списка может выглядеть так:

public interface List<E> {
    int size();
    boolean isEmpty();
    E get(int i) throws IndexOutOfBoundsException;
    E set(int i, E e) throws IndexOutOfBoundsException;
    void add(int i, E e) throws IndexOutOfBoundsException;
    E remove(int i) throws IndexOutOfBoundsException;
}

Интерфейс задаёт операции, которые должна предоставлять любая реализация списка, не фиксируя внутреннее устройство.

1.3.2 ArrayList

ArrayList (список на массиве) хранит все элементы в одном непрерывном массиве. Это даёт отличный random access, но вставки и удаления «в середине» дороги: элементы нужно сдвигать.

Как работают get и set: элементы в массиве — доступ по индексу это одно обращение к памяти, \(O(1)\). Адрес вычисляется как memory_address = base_address + (index × element_size) — по сути мгновенно при любом \(n\).

Как работает add: чтобы вставить в индекс \(i\), все элементы с \(i\) до конца сдвигаются на одну позицию вправо. Почему? В массиве нет «дыры» между соседними ячейками — место нужно физически освободить.

Пример: вставка X в индекс 2 в [A, B, C, D]:

  1. Сдвинуть D в позицию 4: [A, B, C, _, D]
  2. Сдвинуть C в позицию 3: [A, B, _, C, D]
  3. Вставить X в позицию 2: [A, B, X, C, D]

Время \(O(n - i)\): сдвигаем \((n - i)\) элементов. Добавление в конец без сдвига — \(O(1)\).

Как работает remove: удаление в \(i\) сдвигает хвост влево на одну позицию — \(O(n - i)\). Удаление последнего — \(O(1)\).

Динамическое расширение: когда массив заполнен, обычно удваивают ёмкость: новый массив вдвое больше, копирование элементов, затем вставка. Один resize стоит \(O(n)\), но случается редко, поэтому amortized стоимость добавления в конец остаётся \(O(1)\).

Сложность операций ArrayList:

Method Time Complexity
size() \(O(1)\)
isEmpty() \(O(1)\)
get(i) \(O(1)\)
set(i, x) \(O(1)\)
add(i, x) \(O(n - i)\) amortized
addFirst(x) \(O(n)\)
addLast(x) \(O(1)\) amortized
remove(i) \(O(n - i)\)
removeFirst() \(O(n)\)
removeLast() \(O(1)\)

Когда выбирать ArrayList:

  • нужен быстрый доступ по индексу (часто get(i));
  • большинство операций у конца списка;
  • примерно известен ожидаемый размер (меньше лишних resize).

Слабые стороны ArrayList:

  • добавление/удаление в начале — сдвиг всего массива, \(O(n)\);
  • вставка в середину — \(O(n)\).
1.3.3 Односвязный список (singly linked list)

Односвязный список (singly linked list) хранит элементы в отдельных node. В каждом узле:

  • сам элемент (или ссылка на него);
  • ссылка (pointer) на следующий узел.

Первый узел — head, последний — tail; у tail поле next равно null (или \(\emptyset\)).

get и set: до элемента с индексом \(i\) идём от head, следуя \(i\) раз по next — \(O(i)\); «прыгнуть» по индексу нельзя.

add: дойти до узла \(i - 1\), создать новый узел, указывающий на бывший \(i\)-й, и перенастроить ссылку у \((i-1)\)-го — \(O(i)\). Особый случай: вставка в head (\(i=0\)) — новый узел и обновление указателя head, \(O(1)\). Вставка в tail без указателя на хвост — обход до конца, \(O(n)\); с явным tail pointer — \(O(1)\).

remove: дойти до \((i-1)\)-го и «перепрыгнуть» \(i\)-й узел — \(O(i)\). Удаление head — \(O(1)\). Удаление tail всегда \(O(n)\): даже с tail нужен предпоследний узел, а в односвязном списке можно идти только вперёд.

Сложность односвязного списка:

Method Time Complexity
size() \(O(1)\)
isEmpty() \(O(1)\)
get(i) \(O(i)\)
set(i, x) \(O(i)\)
add(i, x) \(O(i)\)
addFirst(x) \(O(1)\)
addLast(x) \(O(n)\) or \(O(1)\) with tail pointer
remove(i) \(O(i)\)
removeFirst() \(O(1)\)
removeLast() \(O(n)\)

Когда выбирать односвязный список:

  • частые добавления/удаления у начала;
  • редкий доступ по индексу;
  • важен объём лишней памяти у ArrayList (незаполненный массив).

Слабые стороны:

  • нет быстрого random access — индекс \(i\) стоит \(O(i)\);
  • удаление с tail — \(O(n)\) даже с tail pointer;
  • на каждый узел — дополнительная память под next.
1.3.4 Двусвязный список (doubly linked list)

Двусвязный список (doubly linked list) похож на односвязный, но у узла есть ссылки и на следующий, и на предыдущий узел — обход в обе стороны.

Обратная ссылка даёт несколько важных следствий:

  • get и set: можно идти с любого конца, сложность \(O(\min(i, n - i))\) — стартуем с того конца, который ближе.
  • add и remove в произвольной позиции: тоже \(O(\min(i, n - i))\) по той же причине.
  • Операции на обоих концах: добавление/удаление у head или tail — \(O(1)\), оба конца доступны напрямую — заметное преимущество перед односвязным списком, где удаление tail — \(O(n)\).

Сложность двусвязного списка:

Method Time Complexity
size() \(O(1)\)
isEmpty() \(O(1)\)
get(i) \(O(\min(i, n - i))\)
set(i, x) \(O(\min(i, n - i))\)
add(i, x) \(O(\min(i, n - i))\)
addFirst(x) \(O(1)\)
addLast(x) \(O(1)\)
remove(i) \(O(\min(i, n - i))\)
removeFirst() \(O(1)\)
removeLast() \(O(1)\)

Когда выбирать двусвязный список:

  • нужны эффективные операции на обоих концах (поведение, похожее на queue);
  • нужен обход в обе стороны;
  • реализация структур вроде deque (double-ended queue).

Компромиссы:

  • больше памяти — два указателя (next и previous) на узел;
  • сложнее реализовать и сопровождать;
  • часто быстрее односвязного списка по операциям, но random access всё ещё медленнее, чем у ArrayList.

Краткое сравнение:

  • ArrayList: лучший random access и операции у конца; когда читаешь заметно чаще, чем меняешь.
  • Singly linked list: частые вставки/удаления у head; когда работа по сути последовательная.
  • Doubly linked list: операции на обоих концах; когда нужна гибкость «с двух сторон».
1.4 Стеки
1.4.1 Stack ADT

Стек (Stack) — ограниченная версия списка: доступ, добавление и удаление только с одного конца — top. Это структура Last-In-First-Out (LIFO): последним пришёл — первым ушёл.

Наглядно: стопка тарелок — кладём и снимаем только сверху; до середины не добраться, пока не снять верхние — именно так ведёт себя Stack.

Зачем ограничивать доступ? Те же операции можно было бы выразить обычным списком, но отдельный интерфейс Stack:

  1. делает код понятнее — видишь Stack, ожидаешь порядок LIFO;
  2. снижает риск ошибок — нельзя случайно залезть в середину;
  3. иногда позволяет более эффективную реализацию.

Stack ADT поддерживает:

  • size() — число элементов;
  • isEmpty() — пуст ли стек;
  • push(x) — положить \(x\) на top;
  • pop() — снять и вернуть верхний;
  • peek() — посмотреть верхний без удаления.

Стеки важны для:

  • рекурсивных вызовов — call stack хранит activation frame;
  • истории посещений — «назад» в браузере, undo;
  • вложенных контекстов в компиляторах.
1.4.2 ArrayStack

ArrayStack — массив и счётчик top для индекса верхнего элемента.

  • Push: увеличить top, записать элемент в data[top].
  • Pop: вернуть data[top], уменьшить top. Для ссылочных типов полезно обнулить data[top + 1] в null, чтобы помочь garbage collection. Почему? GC освобождает память, когда на объект нет ссылок; если в массиве осталась ссылка, объект логически «вышел» из стека, но память может не освободиться.
  • Переполнение: удвоение массива — как у ArrayList.

Все операции \(O(1)\) (push — \(O(1)\) amortized из‑за редкого resize).

1.4.3 LinkedStack

LinkedStack — односвязный список; top совпадает с head.

  • Push: как addFirst — \(O(1)\).
  • Pop: как removeFirst — \(O(1)\).

Все операции на одном конце — односвязного списка достаточно.

Сравнение сложности стека:

Method ArrayStack LinkedStack
size() \(O(1)\) \(O(1)\)
isEmpty() \(O(1)\) \(O(1)\)
push(x) \(O(1)\) amortized \(O(1)\)
pop() \(O(1)\) \(O(1)\)
peek() \(O(1)\) \(O(1)\)

На практике чаще берут ArrayStack: лучше cache locality — элементы подряд в памяти; у связных структур узлы разбросаны, больше cache miss.

1.5 Очереди
1.5.1 Queue ADT

Очередь (Queue) — ограниченный список: добавление с одного конца (rear), удаление с другого (front). Это First-In-First-Out (FIFO): первым пришёл — первым обслужен.

Наглядно: очередь в кассу — новые встают сзади, обслуживают спереди — классическое FIFO.

Противопоставление со Stack: Stack — тарелки (LIFO), Queue — живой ряд (FIFO). Выбор структуры задаёт нужный порядок обработки.

Queue ADT:

  • size(), isEmpty();
  • offer(x) — добавить \(x\) в rear;
  • poll() — снять и вернуть элемент у front;
  • peek() — посмотреть front без удаления.

Очереди для:

  • очередей задач;
  • сообщений в системах и каналах связи;
  • входящих запросов на веб‑серверах.
1.5.2 ArrayQueue и кольцевой массив

Наивный ArrayQueue держит счётчики front и rear: offer двигает rear и кладёт элемент; poll двигает front и возвращает старый front. Проблема: после серии операций «активная» зона ползёт вправо, а начало массива пустует.

Пример:

  • Старт: [A, B, C, _, _] (front=0, rear=2)
  • После poll(): [_, B, C, _, _] (front=1, rear=2)
  • После poll(): [_, _, C, _, _] (front=2, rear=2)
  • После offer(D): [_, _, C, D, _] (front=2, rear=3)
  • После offer(E): [_, _, C, D, E] (front=2, rear=4)
  • Дошли до правого края, а ячейки 0 и 1 пусты.

Решение — circular array: когда rear упирается в конец, он «заворачивается» в начало, если есть место. Индексы считают modulo ёмкости:

\[\text{rear} = (\text{rear} + 1) \mod \text{capacity}\]

Например, ёмкость 5, rear в позиции 4: \((4+1)\bmod 5 = 0\).

При полной очереди — resize (удвоение), как у ArrayList.

Все операции \(O(1)\) (offer — \(O(1)\) amortized).

1.5.3 LinkedQueue

LinkedQueue — односвязный список с tail pointer.

  • Offer: как addLast — \(O(1)\) с tail.
  • Poll: как removeFirst — \(O(1)\).

offer у хвоста, poll у головы — односвязного списка с tail достаточно.

Сравнение сложности очереди:

Method ArrayQueue LinkedQueue
size() \(O(1)\) \(O(1)\)
isEmpty() \(O(1)\) \(O(1)\)
offer(x) \(O(1)\) amortized \(O(1)\)
poll() \(O(1)\) \(O(1)\)
peek() \(O(1)\) \(O(1)\)

Как и со стеками, ArrayQueue часто предпочтительнее из‑за cache locality.

1.6 Рекурсия
1.6.1 Что такое рекурсия?

Рекурсия (recursion) — приём, когда алгоритм сводит задачу к меньшим экземплярам той же задачи. Выделяют:

  • базовый случай (base case): задача настолько мала, что решается сразу (например, \(0! = 1\));
  • рекурсивный случай (recursive case): задача сводится к одной или нескольким меньшим подзадачам тем же алгоритмом.

Наглядно: нужно сосчитать людей в очереди, видя только того, кто прямо перед тобой.

  • База: если ты первый в очереди, верни 1 (только ты).
  • Рекурсия: иначе спроси впереди стоящего «сколько людей впереди тебя?» и прибавь 1.

Каждый решает ту же задачу для более короткой очереди, пока вопрос не дойдёт до первого.

Чтобы рекурсия была корректной:

  1. нужно уменьшение задачи к «меньшей» версии себя;
  2. нужен простой base case;
  3. каждый рекурсивный вызов должен приближать к base case.
1.6.2 Примеры рекурсии

Факториал:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

Как исполняется: проследим factorial(3):

  1. factorial(3) вызывает factorial(2) и умножит результат на 3
  2. factorial(2) вызывает factorial(1) и умножит на 2
  3. factorial(1) вызывает factorial(0) и умножит на 1
  4. factorial(0) сразу возвращает 1 (base case)
  5. factorial(1) получает 1 и возвращает \(1 \times 1 = 1\)
  6. factorial(2) получает 1 и возвращает \(2 \times 1 = 2\)
  7. factorial(3) получает 2 и возвращает \(3 \times 2 = 6\)

Рекурсия «спускается» до base case, затем «поднимается», собирая ответы.

Один base case (\(n = 0\)) и один recursive case с одним рекурсивным вызовом. Время: \(O(n)\) — \(n\) вызовов. Память: \(O(n)\) — глубина call stack (все вызовы «ждут» base case).

Числа Фибоначчи:

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

Два base case и один recursive case с двумя рекурсивными вызовами. Время:

\[T(n) = \begin{cases} 1, & \text{if } n \leq 1 \\ T(n-1) + T(n-2), & \text{otherwise} \end{cases}\]

Верхняя оценка: \(T(n) \leq 2T(n-1) \leq 2^n\), значит \(O(2^n)\); точнее \(T(n) = O(\varphi^n)\), \(\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618\). Память: \(O(n)\) — максимальная глубина стека.

Binary search:

def binsearch(A, l, r, x):
    if l > r:
        return NOT_FOUND
    else:
        mid = (l + r) // 2
        if A[mid] == x:
            return mid
        elif A[mid] > x:
            return binsearch(A, l, mid - 1, x)
        else:
            return binsearch(A, mid + 1, r, x)

Один base case и ветвление, но в каждой ветке — ровно один рекурсивный вызов. Время \(O(\log n)\) — интервал поиска каждый раз делится пополам. Память \(O(\log n)\) из‑за call stack.

1.6.3 Call stack

Рекурсивные функции опираются на call stack — стек среды исполнения. Каждый вызов кладёт activation frame со:

  • сохранёнными локальными переменными;
  • адресом возврата;
  • значениями аргументов.

При возврате кадр снимается, выполнение продолжается в предыдущем кадре. Важно:

  • call stack занимает память — глубокая рекурсия дорога по памяти;
  • слишком глубокая рекурсия даёт stack overflow — стек превышает выделенный лимит.
1.7 Рекурсия и явный стек
1.7.1 Идея

Любой рекурсивный алгоритм можно переписать итеративно, явно моделируя call stack структурой Stack:

  • сохранять состояние текущей функции (аргументы, локальные переменные, метку места в теле) в стеке;
  • вместо рекурсивного вызова — push нового кадра;
  • вместо return из функции — pop верхнего кадра;
  • остановиться, когда стек пуст.
1.7.2 Хвостовая рекурсия (tail recursion)

Функция tail-recursive, если рекурсивный вызов — последняя операция: сразу возвращается результат вызова без дополнительной работы после него. Такие функции проще всего сводятся к циклу: стек по сути не растёт.

Факториал (tail-recursive):

# Recursive
def factorial(n):
    return helper(n, 1)

def helper(n, r):
    if n == 0:
        return r
    else:
        return helper(n - 1, n * r)
# Iterative with explicit stack
def factorial(n):
    s = []  # empty stack
    s.append([n, 1])
    result = None
    while len(s) > 0:
        [n, r] = s.pop()
        if n == 0:
            result = r
        else:
            s.append([n - 1, n * r])
    return result

Стек не длиннее одного элемента — это скрытая tail call optimization.

Binary search тоже tail-recursive, явная стековая версия устроена так же просто.

1.7.3 Не хвостовая рекурсия

Если после рекурсивного вызова остаётся работа, преобразование сложнее: тело делят на стадии (BEFORE, AFTER и т.д.), между кадрами передают result.

Факториал (не хвостовая рекурсия, явный стек):

def factorial(n):
    BEFORE, AFTER = 0, 1
    s = []
    s.append([n, BEFORE])
    result = None
    while len(s) > 0:
        frame = s[-1]  # peek
        if frame[1] == BEFORE:
            frame[1] = AFTER
            if frame[0] == 0:
                result = 1
                s.pop()
            else:
                s.append([frame[0] - 1, BEFORE])
        else:
            n_val = frame[0]
            result = n_val * result
            s.pop()
    return result

Fibonacci (два рекурсивных вызова, явный стек):

При двух вызовах выделяют три стадии: BEFORE, BETWEEN (после первого, до второго), AFTER; промежуточные значения (например, результат первого вызова) хранят в стеке.

def fibonacci(n):
    BEFORE, BETWEEN, AFTER = 0, 1, 2
    s = []
    s.append([n, BEFORE, None])  # [n, state, x]
    result = None
    while len(s) > 0:
        frame = s[-1]  # peek
        if frame[1] == BEFORE:
            if frame[0] <= 1:
                result = frame[0]
                s.pop()
            else:
                frame[1] = BETWEEN
                s.append([frame[0] - 1, BEFORE, None])
        elif frame[1] == BETWEEN:
            frame[2] = result  # save x
            frame[1] = AFTER
            s.append([frame[0] - 2, BEFORE, None])
        else:
            result = frame[2] + result
            s.pop()
    return result
1.8 Полный перебор и backtracking

Brute force — самый прямой подход: перебрать все кандидаты, пока не найдётся решение (или не станет ясно, что его нет). Часто медленно, но если ответ есть, метод его найдёт; удобен как стартовая точка понимания задачи.

Пример: искать книгу на неупорядоченной полке, просматривая подряд — brute force: гарантированно, но долго.

1.8.1 Перебор последовательностей

Базовый приём brute force — сгенерировать все последовательности. Длина \(n\), цифры от \(0\) до \(k\): нужны все строки длины \(n\) над алфавитом \(\{0,\dots,k\}\). Идея — считать в системе счисления с основанием \((k+1)\), пока не дойдём до строки из одних \(k\).

Почему работает: все 3‑битовые двоичные строки (000, …, 111) — это счёт от 0 до 7 в двоичной системе; аналогично для длины \(n\) и цифр \(0..k\) — счёт в базе \((k+1)\).

def all_sequences(n, k):
    A = [0] * n
    finished = False
    while not finished:
        i = n - 1
        while A[i] == k:
            A[i] = 0
            i = i - 1
        if i < 0:
            finished = True
        else:
            A[i] = A[i] + 1
            print(A)

Получаем все \((k+1)^n\) последовательностей.

1.8.2 Перебор подмножеств

Подмножество \(n\) элементов кодируется двоичной строкой длины \(n\): \(i\)-й бит 1, если \(i\)-й элемент входит. Перебор чисел от \(0\) до \(2^n-1\) перечисляет все \(2^n\) подмножеств.

1.8.3 Подмножества с условием на сумму

Дан массив \(A\) из \(n\) целых и цель \(k\); сосчитать число подмножеств \(A\) с суммой ровно \(k\).

Итеративно: перебрать все \(2^n\) битовых строк, поддерживая текущую сумму при смене бита (\(0\to1\): прибавить элемент; \(1\to0\): вычесть). Сравнивать с \(k\).

def subsets(A, n, k):
    S = [0] * n
    finished = False
    total = 0
    count = 0
    while not finished:
        i = n - 1
        while S[i] == 1:
            S[i] = 0
            total = total - A[i]
            i = i - 1
        if i < 0:
            finished = True
        else:
            S[i] = 1
            total = total + A[i]
        if total == k:
            count = count + 1
    return count

Время \(O(2^n)\), память \(O(n)\).

Рекурсивно: пусть \(F(A, k)\) — число подмножеств \(A\) с суммой \(k\). Для пустого множества:

\[F(\emptyset, k) = \begin{cases} 1, & \text{if } k = 0 \\ 0, & \text{otherwise} \end{cases}\]

У \(\emptyset\) сумма 0: если ищем 0, есть ровно одно подмножество — \(\emptyset\); для другой цели — 0 способов.

Для \(A = \{x\} \cup B\):

\[F(\{x\} \cup B, k) = F(B, k) + F(B, k - x)\]

Либо не берём \(x\) — остаток \(B\) должен дать \(k\) → \(F(B,k)\); либо берём \(x\) — остаток должен дать \(k-x\) → \(F(B,k-x)\).

Пример: \(A = \{2, 3, 5\}\), \(k = 5\):

  • без 2: подмножества \(\{3,5\}\) с суммой 5 → \(\{5\}\);
  • с 2: подмножества \(\{3,5\}\) с суммой \(3\) → \(\{3\}\);
  • всего 2 подмножества: \(\{5\}\) и \(\{2,3\}\).
def subsets(A, n, k):
    if n == 0:
        if k == 0:
            return 1
        else:
            return 0
    else:
        x = A[n - 1]
        without_x = subsets(A, n - 1, k)
        with_x = subsets(A, n - 1, k - x)
        return without_x + with_x

Время \(O(2^n)\), память \(O(n)\) — глубина рекурсии.

1.8.4 Backtracking

Backtracking улучшает brute force: не строить сразу все полные решения, а наращивать кандидата по шагам и prune — отбрасывать частичное решение, как только видно, что до валидного полного оно не дотянется.

Аналогия: лабиринт. Brute force нарисует все пути и потом проверит; backtracking идёт шаг за шагом: тупик — откат к последнему разветвлению и другая ветвь.

Плюс: резко меньше узлов перебора. Вместо всех \(n^n\) расстановок ферзей часто достаточно тысяч частично валидных конфигураций.

Задача N Queens:

Классика backtracking: расставить \(n\) ферзей на доске \(n\times n\) так, чтобы не били друг друга (ни одна пара в одной строке, столбце или диагонали).

Почему тяжело: на \(8\times 8\) число способов выбрать 8 клеток из 64 — \(\binom{64}{8} \approx 4{,}4\cdot 10^9\). Backtracking отсекает заведомо плохие частичные расстановки рано.

Наблюдения:

  • в каждой строке ровно один ферзь;
  • для строки \(i\) ищем столбец \(j\), безопасный относительно уже поставленных;
  • если столбца нет — backtrack к строке \(i-1\) и следующий допустимый столбец там.

Дерево поиска: уровень — строка, ветвь — выбор столбца; pruning целых поддеревьев при конфликте эффективнее полного перебора \(n^n\).

Эскиз для \(n = 4\): при переборе с откатами можно получить, например, столбцы [1, 3, 0, 2] для строк \(0,\dots,3\).

def queens(n):
    columns = [0] * n
    i = 0
    while i < n:
        j = columns[i]
        while j < n and not safe(columns, i, j):
            j = j + 1
        if j < n:
            columns[i] = j
            i = i + 1  # Move to next row
        else:
            columns[i] = 0  # Reset this row
            i = i - 1  # Backtrack to previous row
            if i >= 0:
                columns[i] = columns[i] + 1  # Try next column in previous row
    return columns

safe(columns, i, j) проверяет конфликт ферзя в \((i,j)\) с ферзями в строках \(0..i-1\):

  • столбец: был ли уже столбец \(j\);
  • диагональ: для \((r_1,c_1)\) и \((r_2,c_2)\) одна диагональ, если \(|r_1-r_2| = |c_1-c_2|\).

Для \(n=2,3\) решений нет; для \(n=1\) и \(n\ge 4\) — есть.

2. Определения

  • Abstract Data Type (ADT): математическая модель типа данных: какие операции есть, их type signatures и свойства (laws), без фиксации реализации.
  • Data structure: конкретная реализация ADT — представление в памяти и алгоритмы операций.
  • List: ADT упорядоченной последовательности с доступом, вставкой и удалением по индексу.
  • ArrayList: реализация List на непрерывном массиве — \(O(1)\) random access, вставка/удаление в худшем случае \(O(n)\).
  • Singly linked list: узлы со ссылкой next — \(O(1)\) у head, доступ по индексу \(O(n)\) в худшем случае.
  • Doubly linked list: узлы со ссылками next и previous — \(O(1)\) на обоих концах для типовых операций.
  • Head: первый узел связного списка.
  • Tail: последний узел связного списка.
  • Stack: ADT LIFO с доступом только к top; операции push, pop, peek.
  • Queue: ADT FIFO: offer в rear, poll из front; также peek.
  • Circular array: индексация по modulo ёмкости, «хвост» массива смыкается с началом.
  • Recursion: функция решает задачу, вызывая себя на меньших подзадачах; base case даёт прямой ответ.
  • Base case: ветка рекурсии без дальнейших рекурсивных вызовов.
  • Recursive case: сведение к меньшим подзадачам тем же алгоритмом.
  • Call stack: стек среды исполнения с activation frame для каждого активного вызова.
  • Stack overflow: переполнение call stack, часто из‑за слишком глубокой рекурсии.
  • Tail recursion: рекурсивный вызов — последняя операция в ветке; допускает оптимизацию в цикл без роста стека.
  • Amortized complexity: средняя стоимость операции в худшей последовательности с учётом редких дорогих шагов (например resize).
  • Brute force: полный перебор кандидатов с проверкой условия.
  • Backtracking: наращивание кандидата и pruning ветвей, где полного решения уже не получить.
  • Pruning: отсечение целых поддеревьев поиска, если в них нет допустимого решения.

3. Формулы

  • ArrayList, add/remove: \(O(n - i)\), где \(i\) — индекс операции
  • Singly linked list, get/set/add/remove: \(O(i)\)
  • Doubly linked list, get/set/add/remove: \(O(\min(i, n - i))\)
  • Circular array: \(\text{index} = (\text{current} + 1) \mod \text{capacity}\)
  • Fibonacci (время): \(T(n) = T(n-1) + T(n-2)\), сверху \(O(2^n)\); точнее \(O(\varphi^n)\), \(\varphi = \frac{1+\sqrt{5}}{2}\)
  • Binary search: \(T(n) = T(n/2) + O(1) = O(\log n)\)
  • Число последовательностей длины \(n\) с цифрами \(0..k\): \((k+1)^n\)
  • Число подмножеств множества из \(n\) элементов: \(2^n\)
  • Подмножества с суммой: \(F(\{x\} \cup B, k) = F(B, k) + F(B, k - x)\), \(F(\emptyset, k) = [k = 0]\)

4. Примеры

4.1. Разворот DoublyLinkedList за \(O(n)\) (Набор задач 2, Задание 1.1)

Дан DoublyLinkedList \(A\). Напишите псевдокод эффективного метода reverse за \(O(n)\), используя только методы List ADT.

Нажмите, чтобы увидеть решение

Ключевая идея: два указателя — с начала и с конца — и обмен элементов, сходясь к середине.

  1. Индексы: left = 0, right = size() - 1.
  2. Обмен с краёв:
while left < right:
    temp = get(left)
    set(left, get(right))
    set(right, temp)
    left = left + 1
    right = right - 1
  1. Сложность: у DoublyLinkedList операции get/set в позиции \(i\) стоят \(O(\min(i, n-i))\); left у head, right у tail, каждое обращение \(O(1)\) (или близко). \(n/2\) обменов → суммарно \(O(n)\).

Ответ: менять местами пары (left, right), сдвигаясь к центру. Итог: \(O(n)\).

4.2. Разворот ArrayList (Набор задач 2, Задание 1.2)

Оцените временную сложность разворота ArrayList, используя только методы List ADT. Кратко обоснуйте.

Нажмите, чтобы увидеть решение

Ключевая идея: тот же двухуказательный обмен, что в задании 1.

  1. Подход: get и set с двумя указателями с краёв, обмен навстречу.
  2. Сложность: для ArrayList и get(i), и set(i, x) — \(O(1)\); \(n/2\) обменов.

Ответ: \(O(n)\): каждый get/set за \(O(1)\), обменов \(n/2\).

4.3. Разворот LinkedList без tail pointer (Набор задач 2, Задание 1.3)

Оцените сложность разворота LinkedList без tail pointer, только методами List ADT. Кратко обоснуйте.

Нажмите, чтобы увидеть решение

Ключевая идея: на односвязном списке get(i) и set(i, x) стоят \(O(i)\); схема с двумя указателями трогает оба конца.

  1. Подход: обмен get(left) и get(right) при движении к центру.
  2. Цена шага: доступ к индексу right у конца — до \(O(n)\) за раз.
  3. Итог: \(n/2\) обменов × до \(O(n)\) → \(O(n^2)\).

Иначе через remove/add у конца тоже \(O(n)\) без tail.

Ответ: \(O(n^2)\) — много обращений к «хвостовым» индексам.

4.4. Разворот LinkedList с tail pointer (Набор задач 2, Задание 1.4)

Оцените сложность разворота LinkedList с tail pointer, только методами List ADT. Кратко обоснуйте.

Нажмите, чтобы увидеть решение

Ключевая идея: tail pointer помогает addLast и доступу к последнему элементу, но не ускоряет get(i) для произвольного \(i\) — обход всё равно с head.

  1. Подход: как без tail: get(i) и set(i, x) остаются \(O(i)\).
  2. Tail не спасает обмен у конца через get, который всегда идёт с начала.

Ответ: \(O(n^2)\); tail pointer не улучшает get/set по произвольному индексу.

4.5. Разворот ArrayStack (Набор задач 2, Задание 1.5)

Оцените сложность разворота ArrayStack только методами Stack ADT. Кратко обоснуйте.

Нажмите, чтобы увидеть решение

Ключевая идея: при доступных push, pop, peek «увидеть» все элементы можно, снимая их со стека.

  1. Подход: снять всё во вспомогательную структуру (второй стек или массив), затем положить обратно в нужном порядке.
    • Снять все \(n\) в вспомогательный стек \(B\): \(O(n)\) — порядок в \(B\) обращён.
    • Если сразу вернуть из \(B\) в \(A\), восстановится исходный порядок; иногда нужен второй вспомогательный стек \(C\): \(B\to C\to A\).
    • Либо снять в массив и положить обратно в порядке снятия — он уже обратный к исходному.
  2. Только Stack ADT и один дополнительный стек:
    • \(A\to B\) переворачивает последовательность;
    • переложить обратно в \(A\) через ещё один временный контейнер при необходимости;
    • суммарно \(O(n)\).

Ответ: \(O(n)\) — снять все элементы и вернуть в обратном порядке с помощью вспомогательной памяти.

4.6. Разворот LinkedStack (Набор задач 2, Задание 1.6)

Оцените сложность разворота LinkedStack только методами Stack ADT. Кратко обоснуйте.

Нажмите, чтобы увидеть решение

Ключевая идея: как у ArrayStack — тот же Stack ADT.

  1. Подход: снять во вспомогательный стек и переложить обратно.
  2. push/pop у LinkedStack — \(O(1)\).

Ответ: \(O(n)\) — та же схема; каждая операция стека \(O(1)\).

4.7. Разворот ArrayQueue (Набор задач 2, Задание 1.7)

Оцените сложность разворота ArrayQueue только методами Queue ADT. Кратко обоснуйте.

Нажмите, чтобы увидеть решение

Ключевая идея: Queue ADT даёт offer в rear и poll из front; одна очередь сама по себе сохраняет FIFO, разворот неочевиден.

  1. Только одна очередь: «прокрутка» (\(n-1\) раз poll+offer, чтобы протащить последний к front) даёт \(O(n^2)\).
  2. Со вспомогательным стеком: poll всё в стек, затем pop из стека обратно в очередь — стек разворачивает порядок за \(O(n)\), но это уже не «только очередь».
  3. Строго только Queue ADT (без стека и т.п.): разворот — \(O(n^2)\).

Ответ: \(O(n^2)\) при ограничении «только очередь»: каждый элемент нужно многократно протащить через FIFO.

4.8. Разворот LinkedQueue (Набор задач 2, Задание 1.8)

Оцените сложность разворота LinkedQueue только методами Queue ADT. Кратко обоснуйте.

Нажмите, чтобы увидеть решение

Ключевая идея: та же, что у ArrayQueue — идентичный Queue ADT.

  1. Подход: как выше; доступны лишь offer и poll, порядок FIFO жёсткий.
  2. Операции у LinkedQueue по \(O(1)\), но алгоритмическое ограничение то же.

Ответ: \(O(n^2)\) только средствами Queue ADT — по той же причине, что для ArrayQueue.

4.9. Очередь на двух стеках (Набор задач 2, Задание 2)

Предложите реализацию очереди на двух стеках. Приведите псевдокод offer(x) и poll(), обоснуйте корректность и оцените время в худшем случае.

Нажмите, чтобы увидеть решение

Ключевая идея: два стека — inbox для входящих и outbox для исходящих; когда outbox пуст и нужен poll, переложить всё из inbox в outbox (порядок переворачивается второй раз → FIFO на вершине outbox).

  1. Идея: хранить inbox и outbox.
    • offer(x) всегда push в inbox.
    • poll() — pop из outbox; если outbox пуст, сначала перенести все элементы из inbox в outbox (pop/push).
  2. Псевдокод:
class QueueFromStacks:
    inbox = new empty stack
    outbox = new empty stack
        
    def offer(x):
        inbox.push(x)

    def poll():
        if outbox.is_empty():
            while not inbox.is_empty():
                outbox.push(inbox.pop())
        return outbox.pop()
  1. Корректность:
    • offer(x): кладём в inbox; на вершине — последний пришедший (LIFO относительно порядка поступления).
    • poll(): перенос inbox→outbox снова переворачивает порядок, на вершине outbox — самый ранний элемент (FIFO). Пока outbox не пуст, poll снимает в правильном порядке.
  2. Худший случай по времени:
    • offer(x): \(O(1)\) — один push;
    • poll(): до \(O(n)\) — если outbox был пуст, переносим все \(n\) элементов из inbox.
  3. Amortized: каждый элемент делается push/pop не более двух раз (в/из inbox и в/из outbox), amortized на операцию \(O(1)\).

Ответ: два стека (inbox/outbox); offer — \(O(1)\), poll — \(O(n)\) в худшем случае, \(O(1)\) amortized.

4.10. Подсчёт подмножеств размера \(k\) с суммой \(m\) (brute force) (Набор задач 2, Задание 3)

Пусть \(A\) — массив из \(n\) целых. Покажите, как посчитать число способов выбрать \(k\) элементов \(A\) с суммой ровно \(m\), подходом brute force.

  1. Опишите основную идею.
  2. Напишите псевдокод.
  3. Оцените асимптотику времени и кратко обоснуйте.
Нажмите, чтобы увидеть решение

Ключевая идея: перечислить все подмножества размера \(k\) и проверить сумму \(m\). Рекурсивно: для каждого элемента решить «взять / не взять», ведя счётчик размера и остаток суммы.

  1. Идея: рекурсивно (или итеративно) перебрать все \(I \subseteq \{1,\dots,n\}\), \(|I|=k\); для каждого \(I\) вычислить \(\sum_{i\in I} A[i]\) и сравнить с \(m\).
  2. Псевдокод (рекурсия):
def count_subsets(A, n, k, m):
    return helper(A, n, 0, k, m)

def helper(A, n, i, remaining, target):
    if remaining == 0:
        if target == 0:
            return 1
        else:
            return 0
    if i == n:
        return 0
    # Don't include A[i]
    without = helper(A, n, i + 1, remaining, target)
    # Include A[i]
    with_i = helper(A, n, i + 1, remaining - 1, target - A[i])
    return without + with_i
  1. Время: дерево решений глубины \(n\) (включить/исключить); при раннем remaining == 0 есть отсечения. Число листьев порядка \(\binom{n}{k}\), проверка суммы с накоплением — \(O(1)\) на лист. Верхняя грубая оценка вызовов — \(O(2^n)\); точнее по порядку перебора подмножеств размера \(k\) — \(O\!\left(\binom{n}{k}\right)\).

Ответ: рекурсивно перечислить \(\binom{n}{k}\) подмножеств размера \(k\) и считать те, что дают сумму \(m\); время \(O\!\left(\binom{n}{k}\right)\) (сверху также \(O(2^n)\)).

4.11. Факториал (рекурсия) (Лекция 2, Пример 1)

Напишите рекурсивную функцию для \(n!\) и оцените время и память.

Нажмите, чтобы увидеть решение 
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)
  1. Base case: при \(n=0\) возвращаем 1.
  2. Recursive case: \(n \times \text{factorial}(n-1)\).
  3. Время: \(O(n)\) — по одному рекурсивному шагу на уменьшение \(n\).
  4. Память: \(O(n)\) — глубина call stack.

Ответ: время \(O(n)\), память \(O(n)\).

4.12. Фибоначчи (рекурсия) (Лекция 2, Пример 2)

Напишите рекурсивную функцию для \(n\)-го числа Фибоначчи и оцените время.

Нажмите, чтобы увидеть решение 
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
  1. Два base case: \(n=0\to 0\), \(n=1\to 1\).
  2. Recursive case: два рекурсивных вызова.
  3. Время: \[T(n) = T(n-1) + T(n-2) + O(1)\] Сверху \(T(n) \leq 2T(n-1) \leq 2^n\), значит \(O(2^n)\); точнее \(O(\varphi^n)\), \(\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618\).
  4. Память: \(O(n)\) — максимальная глубина рекурсии.

Ответ: время \(O(2^n)\) (точнее \(O(\varphi^n)\)), память \(O(n)\).

4.13. Binary search (рекурсия) (Лекция 2, Пример 3)

Напишите рекурсивный binary search и оцените время и память.

Нажмите, чтобы увидеть решение 
def binsearch(A, l, r, x):
    if l > r:
        return NOT_FOUND
    else:
        mid = (l + r) // 2
        if A[mid] == x:
            return mid
        elif A[mid] > x:
            return binsearch(A, l, mid - 1, x)
        else:
            return binsearch(A, mid + 1, r, x)
  1. Base case: \(l>r\) — элемента нет.
  2. Recursive case: сравнить \(x\) с mid; рекурсия влево или вправо.
  3. Корректность: интервал каждый раз делится пополам; если \(x\) есть в отсортированном массиве, рано или поздно найдём на mid, иначе интервал сожмётся до пустого.
  4. Время: \(T(n)=T(n/2)+O(1)=O(\log n)\).
  5. Память: \(O(\log n)\) из‑за стека (итерация даёт \(O(1)\), т.к. рекурсия tail-recursive).

Ответ: время \(O(\log n)\); память \(O(\log n)\) рекурсивно, \(O(1)\) итеративно.

4.14. Задача N Queens (backtracking) (Лекция 2, Пример 4)

Решите задачу N Queens: расставить \(n\) ферзей на доске \(n\times n\) так, чтобы не делили ни строку, ни столбец, ни диагональ.

Нажмите, чтобы увидеть решение

Ключевая идея: ставить ферзей по строкам; в каждой строке перебирать столбцы; если позиция safe относительно уже поставленных — перейти к следующей строке; иначе backtrack к предыдущей строке и следующему столбцу.

def queens(n):
    columns = [0] * n
    i = 0
    while i >= 0 and i < n:
        j = columns[i]
        while j < n and not safe(columns, i, j):
            j = j + 1
        if j < n:
            columns[i] = j
            i = i + 1           # move to next row
        else:
            columns[i] = 0      # reset this row
            i = i - 1           # backtrack
            if i >= 0:
                columns[i] = columns[i] + 1  # try next column
    return columns

def safe(columns, row, col):
    for r in range(row):
        c = columns[r]
        if c == col:                        # same column
            return False
        if abs(c - col) == abs(r - row):    # same diagonal
            return False
    return True
  1. safe: проверяет конфликт ферзя в (row, col) с ферзями в строках \(0..row-1\).
  2. Backtracking: нет допустимого столбца в строке \(i\) — сброс и возврат к \(i-1\).
  3. Pruning: невалидные ветви отсекаются рано.
  4. Размеры: для \(n=2,3\) решений нет; для \(n=1\) и \(n\ge 4\) — есть.

Ответ: построчная расстановка с backtracking; проверка safe даёт pruning неэффективных ветвей.